public class BinarySearchTree {
    // 创建一颗二叉搜索树
    static class TreeNode{
        // 创建一个三个域的二叉树
        int val;
        public TreeNode left;
        public TreeNode right;

        public TreeNode(int val) {
            this.val = val;
        }
    }

    TreeNode root = null; //根节点

    /**
     *  查找二叉搜索树中指定的val值
     * @param val
     * @return
     */
    // 查找
    // 现在假设已经创建好了一颗搜索二叉树
    public TreeNode find(int val){
        TreeNode cur = root;
        while(cur != null) {
            if (val > cur.val) {
                cur = cur.right;
            } else if (val < cur.val) {
                cur = cur.left;
            } else {
                return cur;
            }
        }
        return null;
    }


    /**
     * 二叉搜索树的插入
     * 插入一个数据
     */
    public void insert(int val){
        if (root == null){
            // 如果一开始就为空 那么就直接插入
            root = new TreeNode(val);
        }
        // 插入是插入到这个二叉树的叶子节点

        //需要定义一个cur
        // 而且必须要记录前一个节点 prev
        TreeNode cur= root;
        TreeNode prev= null;
        while(cur != null){
            if(val > cur.val){
                prev = cur;
                cur = cur.right;
            }else if(val == cur.val){
               return;
            }else {
                prev =cur;
                cur = cur.left;
            }
        }
        TreeNode node = new TreeNode(val);
        if(prev.val < val){
            prev.right = node;
        }else {
            prev.left = node;
        }
    }

    public void inorder(TreeNode root){
        if(root == null){
            return;
        }
        inorder(root.left);
        System.out.print(root.val+" ");
        inorder(root.right);
    }
    /**
     * 删除一个值为val的节点
     */
    public void remove(int val){
        // 有三大种情况
        TreeNode cur = root;
        TreeNode parent = null;
        while(cur != null){
            // 先看cur.val 等不等 val
            if (cur.val == val){
                removeNode(parent,cur);
                return;
            }else if (cur.val < val){
                parent = cur;
                cur = cur.right;
            }else {
                parent = cur;
                cur = cur.left;
            }
        }
    }
    // alt + 回车
    private void removeNode(TreeNode parent, TreeNode cur) {
        if (cur.left == null){
            if(cur == root){
                root = cur.right;
            }else if (parent.left == cur){
                parent.left = cur.right;
            }else {
                parent.right = cur.right;
            }
        }else if(cur.right == null){ //当前cur 没有右树而已 ， 不代表其他的树都没有右树,上面的左树同理
            if(cur == root){
                root = cur.left;
            }else if (parent.left == cur){
                parent.left = cur.left;
            }else {
                parent.right = cur.left;
            }
        }else {
            // cur 左右都不为空的时候
            // 也是最难的

            //1.替换删除
            // 找到一个替罪羊
            // 最好的删除方法是 找到这个待删除的节点 cur 的位置
            // 然后在cur的右边找到一个最小值target.val去交换这个cur
            // 这就需要定义两个节点 targetP 和 target
            // targetP 用来记录 target的父亲节点位置
            // target 用来找最小值
            // targetP 初始值是 cur
            // target 初始值是 cur.right
            // 交换完之后呢 直接将 targetP.left = target.right 就完事了

            TreeNode target = cur.right;
            TreeNode targetParent = cur;
            while(target.left != null){
                targetParent = target;
                target = target.left;
            }
            // 找到之后开始交换
            cur.val = target.val;

            // 删完之后
            // 有两种情况
            if(target == targetParent.left) { // 如果target是targetParent左树的情况
                targetParent.left = target.right;
            }else {// 如果target是targetParent右树的情况
                // TreeNode target = cur.right;
                // TreeNode targetParent = cur;
                // 这就是右树的原因
                targetParent.right = target.right;
            }
        }
    }

}
